package leetcode_题库;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/27 17:14 星期六
 */
public class _101_对称二叉树 {
    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(2);
        TreeNode n2 = new TreeNode(3);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(5);
        TreeNode n7 = new TreeNode(4);
        TreeNode n8 = new TreeNode(8);
        TreeNode n9 = new TreeNode(9);
        TreeNode n10 = new TreeNode(9);
        TreeNode n11 = new TreeNode(8);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6 ;
        n3.right = n7 ;
        n5.left = n8 ;
        n5.right = n9 ;
        n7.left = n10;
        n7.right = n11;

        boolean nn = isSymmetric(n1);
        System.err.println(nn);
    }

    /**
     * 性能很差，但是做出来了，思路比较清晰
     * > 2022/08/27 18:12:05
     * 解答成功:
     * 	执行耗时:1 ms,击败了21.84% 的Java用户
     * 	内存消耗:41.3 MB,击败了5.03% 的Java用户
     * @param root
     * @return
     */
    public static boolean isSymmetric(TreeNode root) {
        //若头结点为空，false
        if (root == null) {
            return false;
        }
        //新队列
        Queue<TreeNode> queue = new ArrayDeque<>();
        //加入头结点
        queue.add(root);
        //队列非空，继续
        while (!queue.isEmpty()) {
            //获取queue中的size，这是这一行的（不是有效数，因为有的地方需要-101占位）
            int size = queue.size();
            //queue中val的集合
            List<Integer> arr = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                //逐次删除，并插入结点val给arr
                TreeNode node = queue.remove();
                arr.add(node.val);
                //若结点val不是-101（取值范围之外，防止雪崩式死循环），说明依然是有效结点，就补全左右支
                if (node.val != -101){
                    //为什么这么做？以该例子为例，最后一行是：null null 8 9 null null 9 8，显然不对称，应该false，若不存哑结点，则8 9 9 8对称，为true，显然不合理。
                    queue.add(node.left != null ? node.left : new TreeNode(-101));
                    queue.add(node.right != null ? node.right : new TreeNode(-101));
                }
            }
            //若size大于1才有比较的意义
            //其一是因为有哑结点的补充，size要么为0（自然不需要判断）要么为大于0的偶数，后续插入不会出现size为奇数的情况。
            //其二是因为第一次头结点例外，它会存入size为1的特殊情况，但是头结点十分特殊，他不存在兄弟结点，我们不应该判断它，所以跳过
            if (size > 1){
                int l = 0;
                int r = arr.size() - 1;
                //双指针，首尾并驱，遇到不一样的直接false
                while (l < r) {
                    if (!arr.get(l).equals(arr.get(r))) {
                        return false;
                    }
                    l++;
                    r--;
                }
            }
        }
        //一定没有问题，true
        return true;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
